#include <stdio.h>
#include <stdlib.h>
/**
*  Tutorial #6 and #7 (Data Structuring Case Study)
*  Program to find maximum and 2nd Maximum and also Sorting of 'n' numbers
**/
int main2()
{
 int n,i,nextMax,min;
 printf("Enter the value of n\n");
 scanf("%d",&n);
 int ar[2*n-1];
 printf("\nEnter the numbers\n");
 for(i=n;i <=(2*n-1);i++){
    scanf("%d",&ar[i]);
 }
 for(i = (2*n-2);i > 1;i =i-2){
    if(ar[i] > ar[i+1]){
        ar[i/2] = ar[i];
    }else{
        ar[i/2] = ar[i+1];
    }
 }
/*
 i = 2;
 while(i<(2*n-1)){
    if(ar[i] > ar[i+1]){
        nextMax = ar[i+1];
        i = i * 2;
    }else{
        nextMax = ar[i];
        i = i + 1;
        i = i * 2;
    }
 }
 printf("Second Largest No is %d\n",nextMax);
 */
 printf("Largest No is %d\n",ar[1]);
 min = getMinimum(ar,n) - 1;
 printf("Sorted Numbers are\n");
 printf("%d",ar[1]);
 printf(", ");
 for(i = 1;i < n;i++){
    printf("%d",getNextMax(ar,n,min));
    printf(", ");
 }
}

int getNextMax(int ar[],int n,int min){
    int i=2,next;
    ar[1] = min;
    while(i < (2*n -1)){
         if(ar[i] > ar[i+1]){
            ar[i] = min;
            i = i * 2;
         }else{
            ar[i+1] = min;
            i = (i + 1)*2;
         }
    }
    for(i = i/2; i > 0 ;i = i/2){
        if(i % 2 == 0){
            if(ar[i] > ar[i+1]){
                ar[i/2] = ar[i];
            }else{
                ar[i/2] = ar[i+1];
            }
        }else{
            if(ar[i] > ar[i-1]){
                ar[i/2] = ar[i];
            }else{
                ar[i/2] = ar[i-1];
            }
        }
    }
    next = ar[1];
    return next;
}

int getMinimum(int ar[],int n){
    int i,min;
    min = ar[n];
    for(i = n+1; i<= (2*n-1);i = i + 2){
        if(ar[i] > ar[i+1] && ar[i+1] < min){
            min = ar[i+1];
        }else if(ar[i] < min){
            min = ar[i];
        }
    }
    return min;
}
